int fun(vector<int>& nums, int target) {
    int l = -1, r = nums.size();
    while (l < r - 1) {
        int mid = (l + r) >> 1;
        if (nums[mid] < target) {
            l = mid;
        } else {
            r = mid;
        }
    }
    return r;
}
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int a = fun(nums, target);
        if ((a < 0 || a >= nums.size()) || nums[a] != target)
            return {-1, -1};
        int b = fun(nums, target + 1) - 1;
        return {a, b};
    }
};

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0,right = nums.size() - 1;
        while(left <= right){
            int mid = (left + right) >> 1;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }
};
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] > target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return right < nums.size() && nums[right] == target ? right : -1;
    }
};
class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int left = 0, right = letters.size() - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (letters[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left < letters.size() ? letters[left] : letters[0];
    }
};
int fun(vector<int>& nums, int target) {
    int l = -1, r = nums.size();
    while (l < r - 1) {
        int mid = (l + r) >> 1;
        if (nums[mid] < target) {
            l = mid;
        } else {
            r = mid;
        }
    }
    return r;
}
class Solution {
public:
    int maximumCount(vector<int>& nums) {
        int a = fun(nums, 0);
        int b = fun(nums, 1);
        cout << a << ' ' << b << endl;
        return max(a,(int)nums.size() - b);
    }
};
int fun(vector<int>& arr2, int target) {
    int left = 0, right = arr2.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr2[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}
class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        sort(arr2.begin(), arr2.end());
        int ans = 0;
        for (auto e : arr1) {
            int a = fun(arr2, e - d);
            int b = fun(arr2, e + d + 1);
            // cout << a << ' ' << b << endl;
            if (a == b)
                ans++;
        }
        return ans;
    }
};
int fun(vector<int>& potions, long long target, int a) {
    int left = 0, right = potions.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if ((long long)potions[mid] * a < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return potions.size() - left;
}
class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions,
                                long long success) {
        vector<int> ans;

        sort(potions.begin(), potions.end());
        for (auto e : spells) {
            ans.push_back(fun(potions, success, e));
        }
        return ans;
    }
};
class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        ranges::sort(nums);
        for(int i = 1;i < nums.size();i++){
            nums[i] += nums[i - 1];
        }
        for(int&x : queries){
            x = ranges::upper_bound(nums,x) - nums.begin();
        }
        return queries;
    }
};
int fun(string& str) {
    vector<int> a(26);
    for (auto& e : str) {
        a[e - 'a']++;
    }
    for (int i = 0; i < 26; i++) {
        if (a[i])
            return a[i];
    }
    return 0;
}
class Solution {
public:
    vector<int> numSmallerByFrequency(vector<string>& queries,
                                      vector<string>& words) {
        vector<int> a, ans;
        for (auto& e : words) {
            a.push_back(fun(e));
        }
        ranges::sort(a);
        for (auto& e : queries) {
            int x = a.end() - ranges::upper_bound(a, fun(e));
            ans.push_back(x);
        }
        return ans;
    }
};
class RangeFreqQuery {
    unordered_map<int, vector<int>> pos;

public:
    RangeFreqQuery(vector<int>& arr) {
        for (int i = 0; i < arr.size(); i++) {
            pos[arr[i]].push_back(i);
        }
    }
    int query(int left, int right, int value) {
        auto t = pos.find(value);
        if (t == pos.end())
            return 0;
        auto& a = t->second;
        return ranges::upper_bound(a, right) - ranges::upper_bound(a, left - 1);
    }
};

/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * RangeFreqQuery* obj = new RangeFreqQuery(arr);
 * int param_1 = obj->query(left,right,value);
 */
 int fun(vector<int>& nums, int end, int target) {
    int left = 0, right = end;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}
class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        ranges::sort(nums);
        long long ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            int a = fun(nums, i - 1, lower - nums[i]);
            int b = fun(nums, i - 1, upper - nums[i] + 1);
            // a = min(a, i);
            // b = min(b, i);
            // cout << a << ' ' << b << endl;
            ans += b - a;
        }
        return ans;
    }
};
class TimeMap {
    unordered_map<string, vector<pair<int, string>>> window;

public:
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        window[key].emplace_back(timestamp, value);
    }

    string get(string key, int timestamp) {
        vector<pair<int, string>>& vv = window[key];
        int left = -1, right = vv.size();
        if(vv.size() == 0 || vv[0].first > timestamp) return "";
        while (left < right - 1) {
            int mid = (left + right) >> 1;
            if (vv[mid].first <= timestamp) {
                left = mid;
            } else {
                right = mid;
            }
            // cout << left << ' ' << right << endl;
        }
        // if (left == -1) {
        //     left++;
        // }
        return vv[left].second;
    }
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */
 class SnapshotArray {
    vector<vector<pair<int, int>>> _vv;
    int _snap_id = -1;

public:
    SnapshotArray(int length) : _vv(length) {}

    void set(int index, int val) { _vv[index].push_back({_snap_id, val}); }

    int snap() { return ++_snap_id; }

    int get(int index, int snap_id) {
        auto& vv = _vv[index];
        if (vv.size() == 0)
            return 0;
        int left = 0, right = vv.size() - 1, ans = 0;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (vv[mid].first < snap_id) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right >= 0 ? vv[right].second:0;
    }
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */
 int myfind(vector<int>& arr, int mode) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] < mode) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;
}
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int a = myfind(arr,x);
        int left = a,right = a + 1;
        while(k--){
            if(right >= arr.size() || (left >= 0 && x - arr[left] <= arr[right] - x))
                left--;
            else
                right++;
        }
        return vector<int>{arr.begin() + left + 1, arr.begin() + right};
    }
};
int NNN = 1e9 + 7;
int binfind(vector<int>& nums, int mode) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (nums[mid] < mode) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    // cout << left << ' ' << right << endl;
    if (right < 0)
        return left;
    if (left >= nums.size())
        return right;
    return mode - nums[right] <= nums[left] - mode ? right : left;
}
class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), sum = 0, t = 0;
        vector<int> tmp(n);
        for (int i = 0; i < n; i++) {
            sum += abs(nums1[i] - nums2[i]);
            sum %= NNN;
            tmp[i] = abs(nums1[i] - nums2[i]);
        }
        ranges::sort(nums1);
        for (int i = 0; i < n; i++) {
            int tt = tmp[i], pos = max(binfind(nums1, nums2[i]), 0);
            // cout << pos << ' ' << tt << endl;
            tt -= abs(nums1[pos] - nums2[i]);
            t = max(t, tt);
            // cout << pos << ' ' << tt << endl;
        }
        return (sum - t + NNN) %NNN;
    }
};
class TopVotedCandidate {
public:
    vector<int> _tops;
    vector<int> _times;
    TopVotedCandidate(vector<int>& persons, vector<int>& times)
        : _times(times) {
        vector<int> p(5001);
        int n = persons.size(), top = 0;
        for (int i = 0; i < n; i++) {
            if (p[top] <= ++p[persons[i]]) {
                top = persons[i];
            }
            _tops.push_back(top);
            // cout << top << ' ';
        }
        // cout << endl;
    }
    int q(int t) {
        int left = 0, right = _times.size() - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (_times[mid] <= t) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // cout << left << ' ' << right << endl;
        return right >= 0 ? _tops[right] : 0;
    }
};

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate* obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj->q(t);
 */
 bool fun(vector<int>& a, vector<int>& b) {
    return a[0] >= b[0] && a[1] >= b[1] && a[2] >= b[2];
}
class Solution {
public:
    vector<int> getTriggerTime(vector<vector<int>>& increase,
                               vector<vector<int>>& requirements) {
        vector<vector<int>> times(increase.size() + 1, vector<int>(3, 0));
        int n1 = increase.size(), n2 = requirements.size();
        for (int i = 0; i < n1; i++) {
            for (int j = 0; j < 3; j++)
                times[i + 1][j] = times[i][j] + increase[i][j];
        }
        vector<int> ans(n2);
        for (int i = 0; i < n2; i++) {
            auto& req = requirements[i];
            if (req[0] > times[n1][0] || req[1] > times[n1][1] ||
                req[2] > times[n1][2]) {
                ans[i] = -1;
                continue;
            }
            int left = 0, right = n1;
            while (left <= right) {
                int mid = (left + right) >> 1;
                if (fun(times[mid], req)) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // cout << left << ' '<< right << endl;
            ans[i] = left;
        }
        return ans;
    }
};